package listbyorder.access301_400.test315;

import java.util.ArrayList;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/3 9:03
 */
// 归并排序加上索引数组求解
public class Solution {

    // 创建所需要的辅助数组
    int[] temps;    // 临时索引数组
    int[] counts;   // 用于保存计算结果的数组
    int[] indexes;  // 排序后的索引数组

    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int n = nums.length;
        if (n == 0) return res;
        temps = new int[n];
        counts = new int[n];
        indexes = new int[n];
        // 计算一个当前的索引数组
        for (int i = 0; i < n; i++) {
            indexes[i] = i;
        }
        // 归并排序并统计
        mergerAndCountSmaller(nums, 0, n - 1);
        // 将counts计算的结果统计到res中
        for (int i = 0; i < n; i++) {
            res.add(counts[i]);
        }
        return res;
    }

    private void mergerAndCountSmaller(int[] nums, int l, int r) {
        if(l == r) return;  //只有一个元素的时候不统计
        int mid = l + (r - l) / 2;
        // 分治
        mergerAndCountSmaller(nums, l, mid);
        mergerAndCountSmaller(nums, mid + 1, r);
        // 归并并进行统计
        if(nums[indexes[mid]] > nums[indexes[mid + 1]]){
            // 前左半部分有序数组的最后一个元素大于右半数组第一个元素的时候，重新进行排序和统计分析
            mergerSortedAnsCountSmaller(nums, l, mid, r);
        }
    }

    private void mergerSortedAnsCountSmaller(int[] nums, int l, int mid, int r) {
        // 首先使用以下当前的临时数组
        for (int i = l; i <= r; i++) {
            temps[i] = indexes[i];   // 临时数组用于保存原始的索引信息，进行合并的时候会根据temps数组更新indexes数组的结构
        }
        // 然后开始排序和统计
        int i = l;
        int j = mid + 1;
        for (int k = l; k <= r; k++) {
            // 从左边向右边更新数组
            if(i > mid){
                indexes[k] = temps[j];
                j++;
            }else if(j > r){
                indexes[k] = temps[i];
                i++;
                counts[indexes[k]] += (r - mid);
            }else if(nums[temps[i]] <= nums[temps[j]]){
                indexes[k] = temps[i];
                i++;
                counts[indexes[k]] += (j - mid - 1);
            }else{
                indexes[k] = temps[j];
                j++;
            }
        }
    }

}
